Minimum Window Substring ​
Minimum Window Substring — LeetCode
Find the smallest substring of s that contains every character of t, including duplicates.
Approach ​
If t is empty or bigger than s, return empty string.
Count the characters in t. Then start counting characters in s. If the character is in t, then check if their counts match. If it matches -> match++ While match == countT.Keys, check if that is the smallest matching string we've seen and update. Move l++. Then remove the count of s[l] from counts. Also check if the match count has changed by checking countS[s[l - 1]] < countT[s[l - 1]] and subtract matches.
Remarks ​
Trick is to know when to start shrinking the left -> when we have a matching string.